package site.wanjiahao.sort.compare;

import site.wanjiahao.sort.Sort;

public class InsertionSort1<E extends Comparable<E>> extends Sort<E> {

    /**
     * 插入排序，将排序数组分为两部分，前部分是已经拍好序的数组，后半部分是待排序的数组
     *      在未排序数组选择当前数组，插入到已经排好序数组的某个位置
     */
    @Override
    protected void sort() {
        for (int i = 1; i < array.length; i++) {
            // 和前面的数据比较，小的话交换，大的话不变
            int cur = i;
            while (cur > 0 && cmp(cur, cur - 1) < 0) {
                // 交换数据
                swap(cur, cur - 1);
                cur--;
            }
        }
    }
}
